Computer Graphics

Output Primitives (Hearn and Baker – Chapter 3)

 

Coordinate Systems

 

Object Space to Image Space Transformations

  1. Set up coordinate system and frame of reference in object space (the space in which the real data is found)
  2. Get the x,y coordinates of each point
  3. Normalize each coordinate to between 0 and 1 by dividing the coordinate by the width or height of the reference frame
  4. Scale the normalized value by the width or height of the drawing area.

 

e.g.

 

 

OpenGL

 

Sample Program

import java.awt.*;

import java.awt.event.*;

 

import net.java.games.jogl.*;

import net.java.games.jogl.util.*;

 

public class HBProg2

{

  public static void main(String[] args)

  {

    Frame frame = new Frame("Lesson 1: An OpenGL Window");

    GLCanvas canvas = GLDrawableFactory.getFactory().createGLCanvas(new GLCapabilities());

    canvas.addGLEventListener(new Renderer());

    frame.add(canvas);

    frame.setSize(400, 300);

   

    frame.addWindowListener(new WindowAdapter()

    {

      public void windowClosing(WindowEvent e)

      {

       

        System.exit(0);

      }

    });

    frame.show();

    canvas.requestFocus();

   

  }

 

  static class Renderer implements GLEventListener, KeyListener

  {

   

   

    public void lineSegment (GL gl)

      {

      gl.glClear (GL.GL_COLOR_BUFFER_BIT);  // Set display window to color.

            gl.glColor3f (0.0f, 0.0f, 0.75f);      // Set line segment color to blue.

      gl.glBegin (GL.GL_LINES);

            gl.glVertex2i (10, 145);

            gl.glVertex2i (180, 15);       // Specify line-segment geometry.

            gl.glEnd ( );

    }

 

   

    public void display(GLDrawable gLDrawable)

    {

      final GL gl = gLDrawable.getGL();

     

      gl.glMatrixMode (GL.GL_MODELVIEW);

      gl.glLoadIdentity();

     

      lineSegment(gLDrawable.getGL());

    

    }

   

   

       public void displayChanged(GLDrawable gLDrawable, boolean modeChanged, boolean deviceChanged)

    {

    }

   

    public void init(GLDrawable gLDrawable)

    {

      final GL gl = gLDrawable.getGL();

      final GLU glu = gLDrawable.getGLU();

           

      gl.glMatrixMode (GL.GL_PROJECTION); 

      gl.glClearColor (1.0f, 1.0f, 1.0f, 0.0f);   //set background to white

      glu.gluOrtho2D (0.0, 200.0, 0.0, 150.0);  // define drawing area

      gLDrawable.addKeyListener(this);

    }

   

       public void reshape(GLDrawable gLDrawable, int x, int y, int width, int height)

    {

     

    }

 

   

    public void keyPressed(KeyEvent e)

    {

      if (e.getKeyCode() == KeyEvent.VK_ESCAPE)

        System.exit(0);

    }

      

    public void keyReleased(KeyEvent e) {}

   

    public void keyTyped(KeyEvent e) {}

      }

 

 

}

 

 

 

 

Points and Lines

Point Plotting

·       convert single coordinate position into device positions

·       load frame buffer with color code

·       low level procedure calls

o      setPixel(x,y)

o      getPixel(x,y)

 

OpenGl Points

GlVertex* ( )

 

glBegin (GL_POINTS);

glVertex* ( );

glEnd ( );

 

 

glBegin (GL_POINTS);

glVertex2i (50, 100);

glVertex2i (75, 150);

glVertex2i (100, 200);

glEnd ( );

 

 

Can use Arrays to hold points

int point1 [ ] = {50, 100};

int point2 [ ] = {75, 150};

int point3 [ ] = {100, 200};

 

glBegin (GL_POINTS);

glVertex2iv (point1);

glVertex2iv (point2);

glVertex2iv (point3);

glEnd ( );

 

Can define point class to define appoint

 

public class wcPt2D {

float x, y;

};

 

Then specify a two-dimensional,world-coordinate point position with the statements

 

wcPt2D pointPos;

pointPos.x = 120.75f;

pointPos.y = 45.30f;

 

glBegin (GL_POINTS);

glVertex2f (pointPos.x, pointPos.y);

glEnd ( );

 

 

Line Drawing

·       Calculate intermediate positions along line path between two specified endpoint positions

·       Load line color into frame buffer

·       Note : true line not at integer values -> aliasing

 

OpenGL Line Drawing

GL_LINES

GL_LINE_STRIP

GL_LINE_LOOP

glBegin (GL_LINES);

  glVertex2iv (p1);

  glVertex2iv (p2);

  glVertex2iv (p3);

  glVertex2iv (p4);

  glVertex2iv (p5);

glEnd ( );

 

glBegin (GL_LINE_STRIP);

  glVertex2iv (p1);

  glVertex2iv (p2);

  glVertex2iv (p3);

  glVertex2iv (p4);

  glVertex2iv (p5);

glEnd ( );

 

glBegin (GL_LINE_LOOP);

  glVertex2iv (p1);

  glVertex2iv (p2);

  glVertex2iv (p3);

  glVertex2iv (p4);

  glVertex2iv (p5);

glEnd ( );

 

 

 

Line Drawing Algorithms

·       Slope-intercept equation ->     y = mx + b

·       Use line segments -> (x1,y1) – (x2,y2)

Slope = m = (y2 – y1)/(x2 –x1)

 

y= [(y2-y1)/(x2-x1)]m +b

 

·       solve for b assuming x1,y1

 

b = y1 – m x1

 

·       Straight line algorithms based on line equation

o      For every interval in x ->  Dx, we can compute  Dy

o      Slope = m =  Dy / Dx  to give 

Dy = m Dx

Dx = Dy / m

·       For vector displays Dx, Dy  can be set to deflection voltages

o      For | m | < 1 set Dx to constant

Dy = m Dx

o      For | m | > 1 set Dy to constant

Dx = Dy / m

 

DDA Line drawing Algorithm

·       General scan conversion problem: which pixels to turn on

o      Assume a line with positive slope in the first octant, i.e., 0.0 <= m <= 1.0.

o      Drawn from left to right: (X1, Y1) to (X2, Y2):

o      Problem: as xi is incremented to xi+1, which pixel gets turned on - xi+1, yi or xi+1, yi+1?

 

 

Digital Differential Analyzer

·       Based on calculating Dx or Dy 

·       Sample line in unit intervals in one direction and calculate increment in other

o      Unit steps are always along the coordinate of greatest change

§       e.g. if Dx = 10 and Dy  = 5, then take unit steps along x and compute steps along y.

§       Assume a line of positive slope from x1, y1 to x2, y2. 

 

if m <= 1.0 then
 
  let x_step = 1 {dx = 1, dy = 0 or 1}
else {m > 1.0}
  let y_step = 1 {dy = 1, x_step = 0 or 1 }
 

 Note: {slope = m = dy/dx}

 

{m <= 1.0} for x_step = 1, dy = m = yi+1 - yi -> yi+1 = yi + m

 

{m > 1} for y_step = 1 m = 1/dx => dx = 1/m => xi+1 = xi + 1/m

 

If, instead, we draw from x2 ,y2 to x1,y1 then:

a.)  dx = -1 yi+1 = yi -m or

b.)  dy = -1 xi+1 = xi - 1/m

 

§       For a line with slope < 0.0 and drawing from x1,y1 to x2,y2, i.e., left to right then:

 

if |m| < 1 then
 let dx = 1 and yi+1 = yi + m
else {|m| ³ 1}
 let dy = -1 and xi+1 = xi -1/m
if draw from x2, y2 to x1, y1 (right to left) then:
 if |m| < 1 then let dx = -1 yi+1 = yi -m
else {|m| ³ 1} dy = 1 xi+1 = xi + 1/m

 

§       Complete DDA Algorithm

procedure DDA( x1, y1, x2, y2: integer);
var
  dx, dy, steps: integer;
  x_inc, y_inc, x, y: real;
begin
  dx := x2 - x1; dy := y2 - y1;
  if abs(dx) > abs(dy) then
     steps := abs(dx); {steps is larger of dx, dy}
  else
     steps := abs(dy);
  x_inc := dx/steps; y_inc := dy/steps;
  {either x_inc or y_inc = 1.0, the other is the slope}
  x:=x1; y:=y1;
  set_pixel(round(x), round(y));
  for i := 1 to steps do
    begin
      x := x + x_inc;
      y := y + y_inc;
      set_pixel(round(x), round(y));
    end;
end; {DDA}

 

§       Example

DDA algorithm calculation

 

 

 

 

 

 

 

 

 

 

 

xa

ya

xb

yb

dx

dy

step

xinc

yinc

 

 

 

 

 

 

2

0

10

5

8

5

8

1.000

0.625

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

step

x

y

xs

ys

 

 

 

 

 

 

 

 

 

 

0

2

0

2

0

 

 

 

 

 

 

 

 

 

 

1

3.000

0.63

3

1

 

 

 

 

 

 

 

 

 

 

2

4.000

1.25

4

1

 

 

 

 

 

 

 

 

 

 

3

5.000

1.88

5

2

 

 

 

 

 

 

 

 

 

 

4

6.000

2.5

6

3

 

 

 

 

 

 

 

 

 

 

5

7.000

3.13

7

3

 

 

 

 

 

 

 

 

 

 

6

8.000

3.75

8

4

 

 

 

 

 

 

 

 

 

 

7

9.000

4.38

9

4

 

 

 

 

 

 

 

 

 

 

8

10.000

5

10

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§       Problems / Concerns:

o      Round-off error

o      FP calculation time

 

OpenGL Version of DDA

import java.awt.*;

import java.awt.event.*;

 

import net.java.games.jogl.*;

import net.java.games.jogl.util.*;

 

public class DDA

{

  public static void main(String[] args)

  {

    Frame frame = new Frame("Lesson 1: An OpenGL Window");

    GLCanvas canvas = GLDrawableFactory.getFactory().createGLCanvas(new GLCapabilities());

    canvas.addGLEventListener(new Renderer());

    frame.add(canvas);

    frame.setSize(400, 300);

   

    frame.addWindowListener(new WindowAdapter()

    {

      public void windowClosing(WindowEvent e)

      {

       

        System.exit(0);

      }

    });

    frame.show();

    canvas.requestFocus();

   

  }

 

  static class Renderer implements GLEventListener, KeyListener

  {

   

   

   public void lineDDA (GL gl, int x0, int y0, int xEnd, int yEnd)

   {

    

      int dx = xEnd - x0,  dy = yEnd - y0,  steps,  k;

      float xIncrement, yIncrement, x = x0, y = y0;

 

      if (Math.abs (dx) > Math.abs (dy))

         steps = Math.abs (dx);

      else

         steps = Math.abs (dy);

 

      xIncrement = (float)dx / (float)steps;

      yIncrement = (float)dy / (float) steps;

 

      setpixel (gl, Math.round (x), Math.round (y));

         

 

      for (k = 0; k < steps; k++) {

         x += xIncrement;

         y += yIncrement;

         setpixel (gl, Math.round (x), Math.round (y));

      }

   }

 

    public void setpixel(GL gl, int x, int y){

       

               gl.glBegin (GL.GL_POINTS);

                 gl.glVertex2i (x, y);

               gl.glEnd ( );

    }

 

   

    public void display(GLDrawable gLDrawable)

    {

     final GL gl = gLDrawable.getGL();

     

      gl.glClear (GL.GL_COLOR_BUFFER_BIT);  // Set display window to color.

               gl.glColor3f (0.0f, 0.0f, 0.75f); 

                   // Set line segment color to blue.

      gl.glMatrixMode (GL.GL_MODELVIEW);

      gl.glLoadIdentity();

     

      lineDDA(gLDrawable.getGL(), 0,0, 200, 150);

    

    }

   

   

         public void displayChanged(GLDrawable gLDrawable, boolean modeChanged, boolean deviceChanged)

    {

    }

   

    public void init(GLDrawable gLDrawable)

    {

      final GL gl = gLDrawable.getGL();

      final GLU glu = gLDrawable.getGLU();

           

      gl.glMatrixMode (GL.GL_PROJECTION); 

      gl.glClearColor (1.0f, 1.0f, 1.0f, 0.0f);   //set background to white

      glu.gluOrtho2D (0.0, 200.0, 0.0, 150.0);  // define drawing area

      gLDrawable.addKeyListener(this);

    }

   

         public void reshape(GLDrawable gLDrawable, int x, int y, int width, int height)

    {

     

    }

 

   

    public void keyPressed(KeyEvent e)

    {

      if (e.getKeyCode() == KeyEvent.VK_ESCAPE)

        System.exit(0);

    }

      

    public void keyReleased(KeyEvent e) {}

   

    public void keyTyped(KeyEvent e) {}

        }

 

 

}

 

 

 

 

Bresenham (Decision Variable) Method

§       Use incremental integer calculations

§       Makes decision of which is next pixel to turn on

§       Look at the center of the pixels

§       Determine d1 and d2 -> the "error", i.e., the difference from the " true line."

§       d1 and d2 specify an integer parameter whose value is proportional to separation of two pixels

 

§       Steps in the Bresenham algorithm:

  1. Determine the error terms
  2. Define a relative error term such that the sign of this term tells which pixel to choose
  3. Derive equation to compute successive error terms from first
  4. Compute first error term

§       Example | m| < 1

o      Sample x at unit intervals

o      Start at (x0,y0) and move to (x1, ?)

o      Must find y closest to line path

o      y is coordinate of true line at xi+1

 

y = m(xi+1) + b

d1 = y - yi = m(xi+1) + b – yi

d2 = (yi+1) - y = yi+1 -m(xi+1) - b

then d1 - d2 = 2m(xi+1) - 2y + 2b -1

§       now define pi = dx(d1 - d2) = relative error of the two pixels.

§       note: pi < 0 if yi pixel is closer

           pi >= 0 if yi+1 pixel is closer

          ( = 0 is our choice).

§       Therefore we only need to know the sign of pi .

§       With m = dy/dx and substituting in for (d1 - d2) we get

(1) pi = 2 * dy * xi - 2 * dx * yi + 2 * dy + dx * (2 * b - 1)

§        let C = 2 * dy + dx * (2 * b - 1)

·       Now look at the relation of p's for successive x terms.

o      pi+1 = 2dy * xi+1 - 2 * dx * y i+1 + C

o      pi+1 - pi = 2 * dy * (xi+1 - xi) - 2 * dx * ( yi+1 - yi)

with xi+1 = xi + 1 and yi+1= yi + 1 or yi

 

(2) pi+1 = pi + 2 * dy - 2 * dx(yi+1 -yi)

Note: b = y - dy / dx * x

·       Now compute p1 (x1,y1) from (1)

p1 = 2dy * x1 - 2dx * y1 + 2dy + dx(2y1 - 2dy / dx * x1 - 1)

= 2dy * x1 - 2dx * y1 + 2dy + 2dx * y1 - 2dyx1 - dx
= 2dy - dx

·       if pi < 0 choose yi and pi+1 = pi + 2dy

·       else {pi >= 0} and choose yi+1 so pi+1 = pi + 2dy - 2dx

 

Bresenham Algorithm for 1st octant:

  1. Enter endpoints (x1, y1) and (x2, y2).
  2. Display x1, y1.
  3. Compute dx = x2 - x1 ; dy = y2 - y1 ; p1 = 2dy - dx.
  4. If p1 < 0.0, display (x1 + 1, y1), else display(x1+1, y1 + 1)
  5. if p1 < 0.0, p2 = p1 + 2dy else p2 = p1 + 2dy - 2dx
  6. Repeat steps 4, 5 until reach (x2, y2).

Note: Only integer Addition and Multiplication by 2. Notice we always increment x by 1.

 

 

For a generalized Bresenham Algorithm must look at behavior in different octants.

Worked Example

 

Bresenham

 

 

 

 

 

 

 

 

xa

ya

xb

yb

dx

dy

2dx

2dy

2dy-2dx

 

20

10

30

18

10

8

20

16

-4

 

 

 

 

 

 

 

 

 

 

 

k

pi

xi+1

yi+1

 

 

 

 

 

 

 

 

20

10

 

 

 

 

 

 

0

6

21

11

 

 

 

 

 

 

1

2

22

12

 

 

 

 

 

 

2

-2

23

12

 

 

 

 

 

 

3

14

24

13

 

 

 

 

 

 

4

10

25

14

 

 

 

 

 

 

5

6

26

15

 

 

 

 

 

 

6

2

27

16

 

 

 

 

 

 

7

-2

28

16

 

 

 

 

 

 

8

14

29

17

 

 

 

 

 

 

9

10

30

18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Applet example of DDA and Bresenham

 

OpenGL version of Bresenham Algorithm

import java.awt.*;

import java.awt.event.*;

 

import net.java.games.jogl.*;

import net.java.games.jogl.util.*;

 

public class Bresenham

{

  public static void main(String[] args)

  {

    Frame frame = new Frame("Bresenham Algorithm");

    GLCanvas canvas = GLDrawableFactory.getFactory().createGLCanvas(new GLCapabilities());

    canvas.addGLEventListener(new Renderer());

    frame.add(canvas);

    frame.setSize(400, 300);

   

    frame.addWindowListener(new WindowAdapter()

    {

      public void windowClosing(WindowEvent e)

      {

       

        System.exit(0);

      }

    });

    frame.show();

    canvas.requestFocus();

   

  }

 

  static class Renderer implements GLEventListener, KeyListener

  {

   

   

    /*  Bresenham line-drawing procedure for |m| < 1.0.  */

 

   public void lineBres (GL gl, int x0, int y0, int xEnd, int yEnd)

   {

      int dx = Math.abs(xEnd - x0),  dy = Math.abs(yEnd - y0);

      int p = 2 * dy - dx;

      int twoDy = 2 * dy,  twoDyMinusDx = 2 * (dy - dx);

      int x, y;

 

      /* Determine which endpoint to use as start position.  */

 

      if (x0 > xEnd) {

         x = xEnd;

         y = yEnd;

         xEnd = x0;

      }

      else {

         x = x0;

         y = y0;

      }

      setpixel (gl, x, y);

 

      while (x < xEnd) {

         x++;

         if (p < 0)

            p += twoDy;

         else {

            y++;

            p += twoDyMinusDx;

         }

         setpixel (gl, x, y);

      }

   }

 

 

    public void setpixel(GL gl, int x, int y){

       

               gl.glBegin (GL.GL_POINTS);

                 gl.glVertex2i (x, y);

               gl.glEnd( );

    }

 

   

    public void display(GLDrawable gLDrawable)

    {

     final GL gl = gLDrawable.getGL();

     

      gl.glClear (GL.GL_COLOR_BUFFER_BIT);  // Set display window to color.

               gl.glColor3f (0.0f, 0.0f, 0.75f); 

                   // Set line segment color to blue.

      gl.glMatrixMode (GL.GL_MODELVIEW);

      gl.glLoadIdentity();

     

      lineBres(gLDrawable.getGL(), 10,25, 180, 100);

    

    }

   

   

         public void displayChanged(GLDrawable gLDrawable, boolean modeChanged, boolean deviceChanged)

    {

    }

   

    public void init(GLDrawable gLDrawable)

    {

      final GL gl = gLDrawable.getGL();

      final GLU glu = gLDrawable.getGLU();

           

      gl.glMatrixMode (GL.GL_PROJECTION); 

      gl.glClearColor (1.0f, 1.0f, 1.0f, 0.0f);   //set background to white

      glu.gluOrtho2D (0.0, 200.0, 0.0, 150.0);  // define drawing area

      gLDrawable.addKeyListener(this);

    }

   

         public void reshape(GLDrawable gLDrawable, int x, int y, int width, int height)

    {

    }

 

   

    public void keyPressed(KeyEvent e)

    {

      if (e.getKeyCode() == KeyEvent.VK_ESCAPE)

        System.exit(0);

    }

      

    public void keyReleased(KeyEvent e) {}

   

    public void keyTyped(KeyEvent e) {}

        }

 

 

}

 

 

Other Geometric Primitives

Points

P1 (x1, y1, z1)

Line Segments

P1 (x1, y1, z1) -> P2 (x2, y2, z2)

Polyline

Connected line segments

Polygons

Closed polyline where initial and terminal points coincide.

Wireframe models

·       Consist of vertices, edges, and polygons (e.g. cube)

·       Stored as vertex list, edge listing, polygon listing

Polyhedron

 

Name

n

m

f

v

e

tetrahedron

3

3

4

4

6

hexahedron

4

3

6

8

12

octahedron

3

4

8

6

12

dodecahedron

5

3

12

20

30

icosahedron

3

5

20

12

30

f,v,e: Faces, Vertices, Edges
n: edges per face
m: faces at each vertex

See Also Visual Geometry Pages

 

Curved Surfaces

Parametric Curves

·       A point P(u) on a curve depends on a parameter u.

·       Since P(u) also depends on an x coordinate and y coordinate, x and y are functions of u with

             P(u) = [ x(u)                  y(u) ]                

·       A parametric representation of a straight line is then

             P(u) = P1 + ( P2 - P1 ) u  where

             x(u) = x1 + ( x2 - x1 ) u                             0 <= u <= 1      

             y(u) = y1 + ( y2 - y1 ) u                             0 <= u <= 1                   

·       e.g. line from P1 (2,2) to P2 (8, 10)

 

Parametric Equation For Straight Line

             from P1 (2,2) to P2(8,10)

u

x(u)

y(u)

0.0

2.0

2.0

0.1

2.6

2.8

0.2

3.2

3.6

0.3

3.8

4.4

0.4

4.4

5.2

0.5

5.0

6.0

0.6

5.6

6.8

0.7

6.2

7.6

0.8

6.8

8.4

0.9

7.4

9.2

1.0

8.0

10.0

 

 

·       e.g. Circle

             x(u) = r cos (2 p u)

             y(u) = r sin (2 p u)

o      Unit circle varying u in increments of 0.05 from 0 to 1.

o      Beginning with P1 (1,0) on the x axis, the circle is built by counterclockwise rotation of point P1 in 2pu (360 degrees u) increments

 

Parametric Equation For Circle of Radius 2.0

u

x(u)

y(u)

0.00

2.00

0.00

0.05

1.90

0.62

0.10

1.62

1.18

0.15

1.18

1.62

0.20

0.62

1.90

0.25

0.00

2.00

0.30

-0.62

1.90

0.35

-1.18

1.62

0.40

-1.62

1.18

0.45

-1.90

0.62

0.50

-2.00

0.00

0.55

-1.90

-0.62

0.60

-1.62

-1.18

0.65

-1.18

-1.62

0.70

-0.62

-1.90

0.75

0.00

-2.00

0.80

0.62

-1.90

0.85

1.18

-1.62

0.90

1.62

-1.18

0.95

1.90

-0.62

1.00

2.00

0.00

 

 

 

 

Curve Design

·       Given n + 1 points => find curve which fits shape

 

·       Try modeling curves using segments  +> use linear combination of basis functions

·       Usually use polynomials => easy to use

·       Polynomials of degree n

·            Continuous piecewise polynomial Q(x) of degree n is a set of k polynomials q(x), each of degree n and k+1 knots (nodes) t0, …, tk ,such that

Q(x) = qi(x)  for all ti <= x <= ti+1 for i = 0, …, k-1

 

·       Polynomials must match or piece together at knots, so…

qi-1(tI ) =  qi-1(ti), i = 0, …, k-1

·       Most useful polynomials are cubic (n =3)

Common Basis Functions

·       e.g. Bezier Curve

·       Bézier curve is a polynomial curve the shape of which is determined by the placement of a series of control points.

·       Figure displays a series of Bézier curves with four control points.

·       Curves begin with a definition of P(u) as

                                                         0 <= u = 1

              

              

 

·       Bi are the control points

·       Jn,i  are the basis or blending functions  which assure the curve travels smoothly from B0  to B3 .

·       Four vertices define a cubic equation with four blending functions.

·       This gives

             J3,0 (u) = ( 1 - u )3

             J3,1 (u) =  3 u ( 1 - u )2

             J3,2 (u) =  3 u2 ( 1 - u )

             J3,3 (u) =  u3          

 

·       P(u) becomes

             P(u) = B0 ( 1 - u )3 + B1 (3 u ( 1 - u )2 ) + B2 (3 u2 ( 1 - u )) + B3 u3

·            x(u) and y(u) are calculated by substituting in the x and y  coordinates of B0 through B3, respectively.

·       Values for u are selected in a uniform way.

·       Figure was calculated with B0 = (1,1), B1 = (2,3), B2 = (4,3), and B3 = (3,1) and varying u from 0 to 1 in 0.05 increments

 

Bézier Curve for

B0(1,1), B1(2,3), B2(4,3), B3(3,1)

u

P(x)

P(y)

0.00

1.00

1.00

0.05

1.16

1.29

0.10

1.33

1.54

0.15

1.50

1.77

0.20

1.69

1.96

0.25

1.88

2.13

0.30

2.06

2.26

0.35

2.25

2.37

0.40

2.42

2.44

0.45

2.59

2.49

0.50

2.75

2.50

0.55

2.89

2.49

0.60

3.02

2.44

0.65

3.12

2.37

0.70

3.20

2.26

0.75

3.25

2.13

0.80

3.27

1.96

0.85

3.26

1.77

0.90

3.21

1.54

0.95

3.13

1.29

1.00

3.00

1.00

 

Quadric Surfaces

·       Sphere

 

Parametric form:

 

·       Ellipsoid

Parametric form:

See also Visual Geometry pages

 

 

·       Torus

 

 

See also Visual Geometry page

 

Parametric Form:

 

·       Superquadrics

o      Super ellipse

o      s = parameter

o      Parametric equations:

 

 

o      Super ellipsoid

Parametric equation:

 

 

 

 

 

Setting a Pixel

·       Initial Task: Turning on a pixel (loading the frame buffer/bit-map)

·       Assume the simplest case, i.e., an 8-bit, non-interlaced graphics system.

·       Then each byte in the frame buffer corresponds to a pixel in the output display.

 

 

·       To find the address of a particular pixel (X,Y):

addr(X, Y) = addr(0,0) + Y rows * (Xm + 1) + X (all in bytes)

o      addr(X,Y) = the memory address of pixel (X,Y)

o      addr(0,0) = the memory address of the initial pixel (0,0)

o      Number of rows = number of raster lines.

o      Number of columns = number of pixels/raster line.

·       Example:

For a system with 640 × 480 pixel resolution, find the address of pixel X = 340, Y = 150

addr(340, 150) = addr(0,0) + 150 * 640 (bytes/row) + 340

= base + 96,340 is the byte location

 

Pixel Addressing and Object Geometry

Object Description:

o      World description –

o      precise coordinate positions

o      infinitesimally small mathematical points

o      Pixel Coordinates

o      Finite screen areas

 

Aligning Approaches

1.     Adjust dimensions of displayed objects to account for amount of overlap of pixel areas with object boundaries

2.     Map world coordinates onto screen positions between pixels to align object boundaries with pixel boundaries instead of centers

 

Screen Grid Coordinates

o      Use horizontal/vertical pixel boundary lines instead of centers

 

    

Old Way -Pixels are line intersections                                     New Way -Pixels are areas

 

Maintaining Geometric Properties of Displayed Objects

·       Geometric objects are transformed into pixels

·       Must account for finite size when transformed to screen

·       Say, we have a line from (20,10) to (30,18)

·       Line precisely ends in real world at (30,18)

·       Pixel extends beyond line

·       Must plot pixels from (20,10) to (29,17) to remain on interior

 

·       Same is true for Rectangle

·       Vertices at (0,0), (4,0), (4,3), (0,3)

 

 

POLYGONS

Polygon

 

Convex polygon – all interior angles of a polygon are less than or equal to 180 degrees.

 

Concave polygon –

 

 

Concave Polygon identification algorithm

o      If z – value of some cross products is positive while others are negative, concave polygon exits.

(assume no three successive vertices are collinear => gives 0 crossproduct)

 

Example:

z-component processing

 

 

(E1 X E2) > 0

(E2 X E3) > 0

(E3 X E4) < 0

(E4 X E5) > 0

(E5 X E6) > 0

(E6 X E7) > 0

 

§       Cross product:

V1 X V2 = u |V1||V2| sinq

where u is unit vector perpendicular to V1 and V2

 

V1 X V2 = ( V1y V2z – V1z V2y, V1z V2x – V1x V2z, V1x V2y – V1y V2x )

 

 

Splitting Concave Polygons

 

 

E1 = (1, 0, 0)

E2 = (1, 1, 0)

E3 = (1, -1, 0)

E4 = (0, 3, 0)

E5 = (-3, 0, 0)

E6 = (0, -3, 0)

 

(E1 X E2) = (0, 0, 1)

(E2 X E3) = (0, 0, -2)

(E3 X E4) = (0, 0, 3)

(E4 X E5) = (0, 0, 9)

(E5 X E6) = (0, 0, 9)

(E6 X E1) = (0, 0, 3)

 

Since E2 X E3 z-value < 0 – must split polygon along line E2

Must determine intersection of line with edge E4

 

Use slope-intercept form of line:

y = max + ba                       y = mbx + bb

max + ba  = mbx + bb

x = ( bb  - ba ) / (ma - mb )

and

x = ( y - ba ) / ma    x = ( y – bb ) / mb

( y - ba ) / ma = ( y – bb ) / mb

y = (ma bb – mb ba ) / (ma - mb )

 

§       Alternative method for splitting concave polygons

1.     Rotational Method:

2.     Proceed counterclockwise

3.     Translate each polygon vertex Vk in sequence to origin

4.     Rotate cloackwise so next vertex is on x axis

5.     If next vector Vk+2 is below axis, polygon is concave

 

e.g.

§       can fined, since (x, y=0), substitute into

x = x1 + ( y – y1 ) / m

so…

x = x1 - y1  / m

 

 

Polygon Tables

 

 

VERTEX TABLE

V1 : x1 , y1 , z1

V2 : x2 , y2 , z2

V3 : x3 , y3 , z3

V4 : x4 , y4 , z4

V5 : x5 , y5 , z5

              

EDGE TABLE

1 : 1 , 2

2 : 2 , 3

3 : 3 , 1

4 : 3 , 4

5 : 4 , 5

6 : 5 , 1

 

SURFACE-FACET TABLE

S 1 : 1 , 2 , 3

S 2 : 3 , 4 , 5 , 6

 

OpenGL Polygon Fill-Area Functions

      glRect* (x1,y1,x2,y2);

e.g.

      glRecti (200,100,50,250);

 

glBegin (GL_POLYGON);

glVertex2iv (p1);

glVertex2iv (p2);

glVertex2iv (p3);

glVertex2iv (p4);

glVertex2iv (p5);

glVertex2iv (p6);

glEnd ( );

 

glBegin (GL_TRIANGLES);

glVertex2iv (p1);

glVertex2iv (p2);

glVertex2iv (p6);

glVertex2iv (p3);

glVertex2iv (p4);

glVertex2iv (p5);

glEnd ( );

 

glBegin (GL_TRIANGLE_STRIP);

glVertex2iv (p1);

glVertex2iv (p2);

glVertex2iv (p6);

glVertex2iv (p3);

glVertex2iv (p5);

glVertex2iv (p4);

glEnd ( );

 

glBegin (GL_TRIANGLE_FAN);

glVertex2iv (p1);

glVertex2iv (p2);

glVertex2iv (p3);

glVertex2iv (p4);

glVertex2iv (p5);

glVertex2iv (p6);

glEnd ( );

 

 

 

 

 

glBegin (GL_QUADS);

glVertex2iv (p1);

glVertex2iv (p2);

glVertex2iv (p3);

glVertex2iv (p4);

glVertex2iv (p5);

glVertex2iv (p6);

glVertex2iv (p7);

glVertex2iv (p8);

glEnd ( );

 

glBegin (GL_QUAD_STRIP);

glVertex2iv (p1);

glVertex2iv (p2);

glVertex2iv (p4);

glVertex2iv (p3);

glVertex2iv (p5);

glVertex2iv (p6);

glVertex2iv (p8);

glVertex2iv (p7);

glEnd ( );